#pragma once
#include<iostream>
enum Colour
{
	red=0,
	black
	
};

template<class T>
struct RBTreeNode
{
	RBTreeNode(const T& data = T())
		: _pLeft(nullptr)
		, _pRight(nullptr)
		, _pParent(nullptr)
		, _data(data)
		, _Colour((Colour)0)
	{}

	RBTreeNode<T>* _pLeft;
	RBTreeNode<T>* _pRight;
	RBTreeNode<T>* _pParent;
	T _data;
	Colour _Colour; // 节点的平衡因子
};

// 请模拟实现红黑树的插入--注意：为了后序封装map和set，本文在实现时给红黑树多增加了一个头结点

template<class T>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	RBTree()
	{
		_pHead = new Node;
		_pHead->_pLeft = _pHead;
		_pHead->_pRight = _pHead;
		_pHead->_Colour = black;
		_pHead->_pParent = nullptr;
	}

	// 在红黑树中插入值为data的节点，插入成功返回true，否则返回false
	// 注意：为了简单起见，本次实现红黑树不存储重复性元素
	bool Insert(const T& data)
	{
		int BLF = 0;
		Node* node = new Node(data);
		if (_pHead->_pParent == nullptr)
		{
			_pHead->_pParent = node;
			node->_Colour = black;
			node->_pParent = _pHead;
			_pHead->_pLeft = node;
			_pHead->_pRight = node;
			return true;
		}
		Node* cur = _pHead->_pParent;
		Node* prev = cur;
		if (node->_data < cur->_data) BLF = 1;
		else  BLF = -1;
		while (cur)
		{
			if (node->_data < cur->_data)
			{
				prev = cur;
				cur = cur->_pLeft;
				if (BLF == -1) BLF = 0;
				
			}
			else 
			{
				prev = cur;
				cur = cur->_pRight;
				if (BLF == 1) BLF = 0;

			}
		}
		if (node->_data < prev->_data)
		{
			prev->_pLeft = node;
			if (BLF == 1) _pHead->_pLeft = node;
		}
		else
		{
			prev->_pRight = node;
			if (BLF == -1) _pHead->_pRight = node;

		}
		node->_pParent = prev;

		//调整开始
		cur = node->_pParent;
		prev = cur->_pParent;
		while(cur->_Colour!=black)
		{
			if (prev->_pLeft == cur)
			{

				if (prev->_pRight && prev->_pRight->_Colour == red)
				{
					cur->_Colour = black;
					prev->_pRight->_Colour = black;
					prev->_Colour = red;
					node = prev;
					cur = node->_pParent;
					prev = cur->_pParent;
				}
				else if (cur->_pLeft == node)
				{
					RotateR(prev);
					cur->_Colour = black;
					prev->_Colour = red;
					node = cur;
					cur = node->_pParent;
					prev = cur->_pParent;
				}
				else 
				{
					RotateL(cur);
					RotateR(prev);
					node->_Colour = black;
					prev->_Colour = red;
					cur = node->_pParent;
					prev = cur->_pParent;
				}
			}
			else
			{

				if (prev->_pLeft && prev->_pLeft->_Colour == red)
				{
					cur->_Colour = black;
					prev->_pLeft->_Colour = black;
					prev->_Colour = red;
					node = prev;
					cur = node->_pParent;
					prev = cur->_pParent;
				}
				else if (cur->_pRight == node)
				{
					RotateL(prev);
					cur->_Colour = black;
					prev->_Colour = red;
					node = cur;
					cur = node->_pParent;
					prev = cur->_pParent;
				}
				else
				{
					RotateR(cur);
					RotateL(prev);
					node->_Colour = black;
					prev->_Colour = red;
					cur = node->_pParent;
					prev = cur->_pParent;
				}
			}
		}
		_pHead->_pParent->_Colour = black;
		
		return true;
	}

	// 检测红黑树中是否存在值为data的节点，存在返回该节点的地址，否则返回nullptr
	Node* Find(const T& data)
	{
		Node* next = _pHead->_pParent;
		while (next)
		{
			if (data < next->_data)
			{
				next = next->_pLeft;
			}
			else if (data > next->_data)
			{
				next = next->_pRight;
			}
			else
			{
				return next;
			}
		}
		return next;
	}

	// 获取红黑树最左侧节点
	Node* LeftMost()
	{
		return _pHead->_pLeft;
	}

	// 获取红黑树最右侧节点
	Node* RightMost()
	{
		return _pHead->_pRight;
	}

	// 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测
	bool IsValidRBTRee()
	{
		if (pRoot == nullptr)
		{
			return false;
		}
		if (pRoot->_Colour != black)
		{
			return false;
		}
		int val=0;
		Node* next = _pHead->_pParent;
		while (next)
		{
			if (next->_Colour == black)
			{
				++val;
			}
			next = next->_pLeft;
		}
		return _IsValidRBTRee(_pHead->_pParent, 0, val);
	}
private:
	bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t pathBlack)
	{
		if (!root)
		{
			if(blackCount!=pathBlack)
				return false;
			return true;
		}
		if (pRoot->_Colour == red && pRoot->_pParent->_Colour == red)
		{
			return false;
		}
		if (pRoot->_Colour == black)
		{
			++blackCount;
		}
		return _IsValidRBTRee(pRoot->_pLeft, blackCount, pathBlack) && _IsValidRBTRee(pRoot->_pRight, blackCount, pathBlack);
	}
	// 左单旋
	void RotateL(Node* pParent)
	{
		Node* hParent = pParent->_pParent;
		Node* pRight = pParent->_pRight;
		if (hParent==_pHead)
		{
			_pHead->_pParent = pRight;
		}
		if (hParent != _pHead)
		{
			if (hParent->_pLeft == pParent)
			{
				hParent->_pLeft = pRight;
			}
			else
			{
				hParent->_pRight = pRight;
			}
		}

		pParent->_pParent = pRight;
		pParent->_pRight = pRight->_pLeft;
		if (pRight->_pLeft)
		{
			pRight->_pLeft->_pParent = pParent;
		}

		pRight->_pParent = hParent;
		pRight->_pLeft = pParent;

	}
	// 右单旋
	void RotateR(Node* pParent)
	{
		Node* hParent = pParent->_pParent;
		Node* pLeft = pParent->_pLeft;
		if (hParent==_pHead)
		{
			_pHead->_pParent = pLeft;
		}
		if (hParent != _pHead)
		{
			if (hParent->_pLeft == pParent)
			{
				hParent->_pLeft = pLeft;
			}
			else
			{
				hParent->_pRight = pLeft;
			}
		}

		pParent->_pParent = pLeft;
		pParent->_pLeft = pLeft->_pRight;
		if (pLeft->_pRight)
		{
			pLeft->_pRight->_pParent = pParent;
		}

		pLeft->_pParent = hParent;
		pLeft->_pRight = pParent;


	}
	// 为了操作树简单起见：获取根节点
	Node*& GetRoot()
	{
		return _pHead->_pParent;
	}
private:
	Node* _pHead;
};